#include <vector>
#include <iostream>

// 将src顶部的盘挪到tar中
void move(std::vector<int>& src,std::vector<int>& tar) {
    int pan = src.back();
    src.pop_back();
    tar.push_back(pan);
}

void dfs(int i,std::vector<int>& src,std::vector<int>& buf,std::vector<int>& tar) {
    // 如果src中只有一个盘了，直接挪到tar中
    if(i == 1) {
        move(src,tar);
        return;
    }
    // 借助tar,将src中的i-1个盘挪到buf中
    dfs(i-1,src,tar,buf);
    // 将src顶部的一个盘挪到tar中
    move(src,tar);
    // 借助src,将buf中的i-1个盘挪到tar中
    dfs(i-1,buf,src,tar);
}

void Hannota(std::vector<int>& src,std::vector<int>& buf,std::vector<int>& tar) {
    int n = src.size();
    dfs(n,src,buf,tar);
    return;
}
int main() {
    // 汉诺塔问题，借助buf将src中的盘全部转移到tar中
    std::vector<int> src = {1,2,3,45,53};
    std::vector<int> buf;
    std::vector<int> tar;
    Hannota(src,buf,tar);
    std::cout << "tar: ";
    for(int i = 0;i < tar.size();i++) {
        std::cout << tar.at(i) <<" ";
    }
    return 0;
}